/**
 * @Author: wangliuyang
 * @Date: 2021/8/18 22:58
 * @Description:123. 买卖股票的最佳时机 III
 */
public class Solution_123 {
    public int maxProfit(int[] prices,int k) {
        int length = prices.length;
        int[][] dp = new int[length][k + 1];
        for (int j = 1; j < k + 1; j++) {
            int t = dp[0][j] - prices[0];
            for (int i = 1; i < dp.length; i++) {
                int temp = Math.max(dp[i][j - 1],t + prices[i]);
                dp[i][j] = Math.max(temp,dp[i - 1][j]);
                t = temp - prices[i];
            }
        }
        return dp[length - 1][k];
    }
}
